package my;

import my.graph.Graph;
import my.graph.Graph.PathInfo;
import my.graph.Graph.WeightManager;
import my.graph.ListGraph;
import my.util.Data;

import java.util.Map;

/**
 * Graph Test
 *
 * @author AJun
 * @date 2020/11/9
 */
public class Main18 {

    public static void main(String[] args) {
        // 基本接口
        // testListGraph1();
        // testListGraph2();

        // 遍历
        // testBfs();
        // testDfs();

        // 拓扑排序
        // testTopology();

        // 最小生成树
        // testMst();

        // 单源最短路径
        // testShortestPath();

        // 多源最短路径
        testMultiSp();
    }

    static void testMultiSp() {
        Graph<Object, Double> graph = directedGraph(Data.NEGATIVE_WEIGHT1);
        Map<Object, Map<Object, PathInfo<Object, Double>>> sp = graph.shortestPath();
        sp.forEach((Object from, Map<Object, PathInfo<Object, Double>> paths) -> {
            System.out.println(from + "---------------------");
            paths.forEach((Object to, PathInfo<Object, Double> path) -> {
                System.out.println(to + " - " + path);
            });
        });
    }

    private static void testShortestPath() {
        Graph<Object, Double> graph = undirectedGraph(Data.SP);
        Map<Object, PathInfo<Object, Double>> shortestPath = graph.shortestPath("A");
        if (shortestPath == null) {
            return;
        }
        shortestPath.forEach((v, path) -> {
            System.out.println(v + " - " + path);
        });
    }

    private static void testMst() {
        Graph<Object, Double> graph = undirectedGraph(Data.MST_01);
        graph.mst().forEach(System.out::println);
    }

    private static void testTopology() {
        Graph<Object, Double> graph = directedGraph(Data.TOPO);
        graph.topologicalSort().forEach(System.out::println);
    }

    private static void testBfs() {
        Graph<Object, Double> graph = directedGraph(Data.BFS_02);
        graph.bfs(0, o -> {
            System.out.println(o);
            return false;
        });
    }

    private static void testDfs() {
        Graph<Object, Double> graph = directedGraph(Data.DFS_02);
        graph.dfs("a", o -> {
            System.out.println(o);
            return false;
        });
    }

    /**
     * 权重管理者
     */
    static WeightManager<Double> weightManager = new WeightManager<Double>() {
        public int compare(Double w1, Double w2) {
            return w1.compareTo(w2);
        }

        public Double add(Double w1, Double w2) {
            return w1 + w2;
        }

        @Override
        public Double zero() {
            return 0.0;
        }
    };

    /**
     * 有向图
     */
    private static Graph<Object, Double> directedGraph(Object[][] data) {
        Graph<Object, Double> graph = new ListGraph<>(weightManager);
        for (Object[] edge : data) {
            if (edge.length == 1) {
                graph.addVertex(edge[0]);
            } else if (edge.length == 2) {
                graph.addEdge(edge[0], edge[1]);
            } else if (edge.length == 3) {
                double weight = Double.parseDouble(edge[2].toString());
                graph.addEdge(edge[0], edge[1], weight);
            }
        }
        return graph;
    }

    /**
     * 无向图
     */
    @SuppressWarnings("SameParameterValue")
    private static Graph<Object, Double> undirectedGraph(Object[][] data) {
        Graph<Object, Double> graph = new ListGraph<>(weightManager);
        for (Object[] edge : data) {
            if (edge.length == 1) {
                graph.addVertex(edge[0]);
            } else if (edge.length == 2) {
                graph.addEdge(edge[0], edge[1]);
                graph.addEdge(edge[1], edge[0]);
            } else if (edge.length == 3) {
                double weight = Double.parseDouble(edge[2].toString());
                graph.addEdge(edge[0], edge[1], weight);
                graph.addEdge(edge[1], edge[0], weight);
            }
        }
        return graph;
    }

    private static void testListGraph1() {
        Graph<String, Integer> graph = new ListGraph<>();
        graph.addEdge("V1", "V0", 9);
        graph.addEdge("V1", "V2", 3);
        graph.addEdge("V2", "V0", 2);
        graph.addEdge("V2", "V3", 5);
        graph.addEdge("V3", "V4", 1);
        graph.addEdge("V0", "V4", 6);

        // graph.removeEdge("V0", "V4");
        // graph.removeVertex("V0");
        // graph.bfs("V1");

        graph.print();
    }

    private static void testListGraph2() {
        Graph<String, Integer> graph = new ListGraph<>();
        graph.addEdge("V0", "V1");
        graph.addEdge("V1", "V0");

        graph.addEdge("V0", "V2");
        graph.addEdge("V2", "V0");

        graph.addEdge("V0", "V3");
        graph.addEdge("V3", "V0");

        graph.addEdge("V2", "V1");
        graph.addEdge("V1", "V2");

        graph.addEdge("V2", "V3");
        graph.addEdge("V3", "V2");

        graph.print();
    }

}
